Problems tagged with "depth first search"

What is the time complexity of depth first search (DFS) when run on a tree with \(n\) nodes?

Suppose an undirected graph \(G = (V, E)\) is a tree with 33 edges. Suppose a node \(s\) is used as the source of a depth-first search.

Including the root call of dfs on node \(s\), how many calls to dfs will be made?

Let \(G = (V, E)\) be an undirected tree.

Suppose breadth-first search (BFS) and depth-first search (DFS) are each run on the graph using the same source node. True or False: for any node \(u\) in the graph, the BFS predecessor of \(u\) and the DFS predecessor of \(u\) must be the same.

Suppose both BFS and DFS are run on the same graph \(G = (V, E)\) using the same source node. Assume that \(G\) is a tree. Consider a particular node \(u\) in the graph. True or False: the BFS predecessor found for \(u\) and the DFS predecessor found for \(u\) must be the same.

We saw in lecture that both full BFS and DFS produce trees when run on connected graphs, and forests when run on disconnected graphs. Suppose a full BFS and a full DFS are run on an undirected graph with three connected components. True or False: the number of trees in the BFS forest will equal to number of trees in the DFS forest.

Suppose a depth first search (DFS) is run on the graph shown below using node \(u_4\) as the source and the convention that graph.neighbors produces nodes in ascending order by label. What will be the predecessor of \(u_6\) in the DFS?

Suppose a depth first search is run on the graph shown below using node \(u_4\) as the source, and adopt the convention that graph.neighbors produces nodes in ascending order of label. Which node will have the smallest finish time?

Suppose a depth first search is run on the graph shown below using node \(u_4\) as the source, and adopt the convention that graph.neighbors produces nodes in ascending order of label. What will be the start time of node \(u_7\)?

Suppose a depth first search is run on the graph below using node \(d\) as the source, and using the convention that a node's neighbors are produced in alphabetical order.

What is the predecessor of node \(v\) in the DFS search tree?

Suppose a depth first search is run on the graph below in order to find start and finish times using node \(d\) as the source.

Adopt the convention that the first start time is 1, and, as always, that neighbors are produced in ascending order by label. What will be the start and finish times of node \(r\)?

Suppose a DFS is run on the graph shown below using node 11 as the source.

What will be the DFS predecessor of node 3 in the search? Use the convention that a node's neighbors are produced in ascending order by label.

Suppose a DFS is run on the graph shown below using node 11 as the source. Use the convention that a node's neighbors are produced in ascending order by label.

Suppose a depth first search (DFS) is run on the graph below, starting at node \(a\). Start and finish times are calculated using the convention that the start time of node \(a\) is 1.

What will be the finish time of node \(c\)? Assume the convention that a node's neighbors are produced in alphabetical order.

Suppose a depth first search (DFS) is run on the graph below, starting at node \(a\). Start and finish times are calculated using the convention that the start time of node \(a\) is 1.

What will be the finish time of node \(e\)? Assume the convention that a node's neighbors are produced in alphabetical order.

Suppose a depth-first search (DFS) is run on the graph shown below using node \(s\) as the source and adopting the convention that a node's neighbors are produced in ascending order of their label.

A modification of the dfs function from lecture is shown below. It is the same as the original dfs function, except that it has an added print statement.

def dfs(graph, u, status=None):
    """Start a DFS at `u`."""
    # initialize status if it was not passed
    if status is None:
        status = {node: 'undiscovered' for node in graph.nodes}
    status[u] = 'pending'
    for v in graph.neighbors(u):
        if status[v] == 'undiscovered':
            print("Hello!")
            dfs(graph, v, status)
    status[u] = 'visited'

Consider running this algorithm on the following graph, starting at node \(a\):

How many times will "Hello!" be printed? Note that this is not a full DFS, and that not all nodes are reachable from \(a\).

A modification of the dfs function from lecture is shown below. It is the same as the original dfs function, except that it has an added print statement.

def dfs(graph, u, status=None):
    """Start a DFS at `u`."""
    # initialize status if it was not passed
    if status is None:
        status = {node: 'undiscovered' for node in graph.nodes}
    status[u] = 'pending'
    for v in graph.neighbors(u):
        print("Hello!")
        if status[v] == 'undiscovered':
            dfs(graph, v, status)
    status[u] = 'visited'

Consider running this algorithm on the following graph, starting at node \(a\):

How many times will "Hello!" be printed? Note that this is not a full DFS, and that not all nodes are reachable from \(a\).

Consider the code shown below. It shows DFS as seen in lecture, with one modification: a print statement in the for-loop.

def dfs(graph, u, status=None):
    """Start a DFS at `u`."""
    # initialize status if it was not passed
    if status is None:
        status = {node: 'undiscovered' for node in graph.nodes}
    status[u] = 'pending'
    for v in graph.neighbors(u):
        print("Hello!")
        if status[v] == 'undiscovered':
            dfs(graph, v, status)
    status[u] = 'visited'

How many times will "Hello!" be printed if dfs is run on the graph below using node \(u\) as the source? Note that dfs will not be restarted if the first call does not explore the whole graph.

Suppose we define a forward-looking graph with \(n\) nodes to be the directed graph \(G = (V, E)\) with nodes \(u_1, \ldots, u_n\) and the edge \((u_i, u_j)\) if and only if \(i < j\). An example of such a graph with 4 nodes is shown below.

What is the time complexity of depth-first search when run on a forward-looking graph with \(n\) nodes, using node \(u_1\) as the source? State your answer as a function of \(n\) using asymptotic notation.

Suppose you run DFS on a graph in which all nodes are reachable from the source node. True or false: the source node will be marked as visited last, only if the graph is undirected.

Suppose a DFS is run on a directed graph. Let \(u\) and \(v\) be two nodes in the graph, and assume that the edge \((u, v)\) exists. True or False: it is possible that, at some moment in time, \(u\) is marked as ``visited'' while \(v\) is marked as ``undiscovered''.

Suppose a depth first search is run on a directed graph. True or False: it is possible that, at any moment in time, there is a node marked as visited which has a neighbor (successor) that is marked as pending.

Suppose that a depth first search is being performed on an undirected graph, and when dfs is called on a node \(u\), the statuses of all of its neighbors are printed. True or False: it is possible that one of the neighbors is marked as ``visited''.

Suppose a depth first search (DFS) is run on a connected undirected graph, and there is a node \(u\) which has only one neighbor. True or False: the finish time of node \(u\) will be equal to its start time plus 3.

In a DFS on an undirected graph \(G\), the start time of node \(u\) is 12, while the finish time of node \(u\) is 37. How many nodes were marked pending between the moment that node \(u\) was marked pending and the moment that it was marked visited? Node \(u\) itself should be excluded from your count.

Suppose \(T = (V, E)\) is a connected, undirected graph with no cycles (that is, \(T\) is a tree). Suppose a depth first search is run on \(T\) using node s as the source. Assume that node s has two neighbors: \(u\) and \(v\). If \(|V| = 15\), which one of the below represents possible start and finish times of \(u\) and \(v\)? You may assume that graph.neighbors produces neighbors in ascending order of label.

Let \(G\) be a graph, and suppose \(s\), \(u\), and \(v\) are three nodes in the graph.

Suppose a depth-first search (DFS) is run on \(G\) using node \(s\) as the source and adopting the convention that a node's neighbors are produced in ascending order by label. During this DFS, start and finish times are computed. Suppose it is found that:

Now suppose another DFS is run using node \(s\) as the source, but adopting a different convention about the order in which neighbors are produced. Suppose new_start and new_finish are the start and finish times found by this second DFS. True or False: it must be that

Suppose \(v\) is reachable from node \(u\) in a directed graph. A DFS is run on the graph, and node \(u\) is discovered before node \(v\) (its start time is less than \(v\)'s start time). True or false: the finish time of node \(v\) must be less than the finish time of node \(u\).

True or False: a depth first search with source node \(s\) is guaranteed to find the longest simple path starting from \(s\) in a connected, undirected graph \(G\) That is, suppose that there is a unique longest simple path in \(G\), and call this path \(p\). True or False: the longest simple path in the DFS forest must be also be \(p\).